//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 770 👎 0

package leetcode.editor.cn;

import java.util.*;

class ShuZuZhongDeNiXuDuiLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongDeNiXuDuiLcof().new Solution();
        solution.reversePairs(new int[]{2147483647, 2147483647, -2147483647, -2147483647, -2147483647, 2147483647});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int reversePairs(int[] nums) {
            if (nums.length == 1) return 0;
            this.nums = nums;
            tmp = new int[nums.length];
            return mergeSort(0, nums.length - 1);
        }

        int[] nums, tmp;

        public int mergeSort(int l, int r) {
            if (l >= r) {
                return 0;
            }

            // 递归划分
            int mid = (r + l) / 2;
            int res = mergeSort(l, mid) + mergeSort(mid + 1, r);

            for (int i = l; i <= r; i++) {
                tmp[i] = nums[i];
            }

            // 开始合并
            int i = l, j = mid + 1;
            for (int k = l; k <= r; k++) {
                if (i == mid + 1) {
                    nums[k] = tmp[j++];
                    // 注意使用tmp来比较，num会被覆盖
                } else if (j == r + 1 || tmp[j] >= tmp[i]) {
                    nums[k] = tmp[i++];
                } else {
                    nums[k] = tmp[j++];
                    res += mid - i + 1;
                }
            }

            return res;
        }

        // 回溯超时
    /*int count = 0;
    LinkedList<Integer> path = new LinkedList<>();

    public void traversal(int[] nums, int startIndex, boolean[] used) {
        if (path.size() == 2) {
            count++;
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            if (used[i] == true) continue;
            if (!path.isEmpty() && Integer.compare(nums[i], path.getLast()) >= 0) continue;
            used[i] = true;
            path.add(nums[i]);
            traversal(nums, i + 1, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
